/*
 * Project: Sudoku Explainer
 * Copyright (C) 2006-2007 Nicolas Juillerat
 * 
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver;

import java.security.AccessControlException;
import java.util.ArrayList;
import java.util.List;

import android.content.Context;

import com.onegravity.sudoku.solver.accumulator.DefaultHintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.FinalHintInterceptor;
import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.SingleHintAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.checks.Analyzer;
import com.onegravity.sudoku.solver.checks.IncorrectDigitsProducer;
import com.onegravity.sudoku.solver.checks.IncorrectPencilMarksProducer;
import com.onegravity.sudoku.solver.checks.MissingPencilMarksProducer;
import com.onegravity.sudoku.solver.checks.NoHintsWarning;
import com.onegravity.sudoku.solver.checks.PencilMarks2EliminateProducer;
import com.onegravity.sudoku.solver.checks.SolutionProducer;
import com.onegravity.sudoku.solver.checks.TooFewGivensProducer;
import com.onegravity.sudoku.solver.core.FinalHint;
import com.onegravity.sudoku.solver.core.Hint;
import com.onegravity.sudoku.solver.core.HintProducer;
import com.onegravity.sudoku.solver.core.Rule;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.rules.AlignedPairExclusionProducer;
import com.onegravity.sudoku.solver.rules.AlignedSubsetExclusionProducer;
import com.onegravity.sudoku.solver.rules.BruteForceProducer;
import com.onegravity.sudoku.solver.rules.SueDeCoqProducer;
import com.onegravity.sudoku.solver.rules.als.ALCProducer;
import com.onegravity.sudoku.solver.rules.als.ALSProducer;
import com.onegravity.sudoku.solver.rules.chaining.ChainProducer;
import com.onegravity.sudoku.solver.rules.fish.FishProducer;
import com.onegravity.sudoku.solver.rules.fish.LockingProducer;
import com.onegravity.sudoku.solver.rules.hidden.HiddenSingleProducer;
import com.onegravity.sudoku.solver.rules.hidden.HiddenSubsetProducer;
import com.onegravity.sudoku.solver.rules.naked.NakedSingleProducer;
import com.onegravity.sudoku.solver.rules.naked.NakedSubsetProducer;
import com.onegravity.sudoku.solver.rules.uniqueness.AvoidableRectangleProducer;
import com.onegravity.sudoku.solver.rules.uniqueness.BUGProducer;
import com.onegravity.sudoku.solver.rules.uniqueness.HiddenUniqueRectangleProducer;
import com.onegravity.sudoku.solver.rules.uniqueness.UniquenessTestProducer;
import com.onegravity.sudoku.solver.rules.wing.WWingProducer;
import com.onegravity.sudoku.solver.rules.wing.WingProducer;
import com.onegravity.sudoku.solver.util.Logger;

/**
 * The HintEngine to collect hints, to analyze and solve Sudokus.
 */
public class HintEngine {

	private static Context sContext;
	
	private SolvingTechniquesConfig mConfig;
    private boolean mEliminatePencilMarks;
	private Grid mGrid;
    private Grid mSolvedGrid;
    private boolean mIsBeyondNightmare;
    
    transient private List<HintProducer> hintProducers;
    transient private List<HintProducer> checkProducers;
    transient private List<HintProducer> solveProducers;
    transient private List<HintProducer> analyzeProducers;
    transient private List<HintProducer> analyzeDifficultyProducers;

    public static void initializeHintEngine(Context context) {
    	HintEngine.sContext = context;
    }
    
    public static Context getContext() {
    	return sContext;
    }
    
    /**
     * 
     * @param config If null a default config will be used with all solving techniques enabled
     * @param grid The grid, may not be null
     * @param isBeyondNightmare
     * @param solvedGrid The solved grid, may be null
     */
    public HintEngine(SolvingTechniquesConfig config, Grid grid, boolean isBeyondNightmare, Grid solvedGrid) {
    	this(config, false, grid, isBeyondNightmare, solvedGrid);
    }

    /**
     * 
     * @param config If null a default config will be used with all solving techniques enabled
     * @param grid The grid, may not be null
     * @param eliminatePencilMarks if True pencil marks are being labeled as "to be eliminated" instead of being marked as incorrect,
     * 							   if they violate the Sudoku rules (same digit in row, column, block, extra region).
     * 							   The message to the player is: "there are pencil marks that can be removed" instead of
     * 							   "these pencil marks are incorrect"
     * @param isBeyondNightmare
     * @param solvedGrid The solved grid, may be null
     */
    public HintEngine(SolvingTechniquesConfig config, boolean eliminatePencilMarks, Grid grid, boolean isBeyondNightmare, Grid solvedGrid) {
    	mConfig = (config==null) ? new SolvingTechniquesConfig() : config;
        mGrid = grid;
        mIsBeyondNightmare = isBeyondNightmare;
        mSolvedGrid = solvedGrid;
        mEliminatePencilMarks = eliminatePencilMarks;
    }

    /**
     * Return producers to compute hints 
     */
    private ArrayList<HintProducer> getHintProducers(Grid solvedGrid) {
    	ArrayList<HintProducer> producers = new ArrayList<HintProducer>();

        // (1) first we check for incorrect & too few digits & incorrect pencil marks
    	if (solvedGrid==null) {
    		producers.add(new SolutionProducer(false)); // no solution --> check details with SolutionProducer 
    	}
        producers.add(new IncorrectDigitsProducer(solvedGrid, true));
    	producers.add(new TooFewGivensProducer());
    	if (mEliminatePencilMarks) {
            producers.add(new PencilMarks2EliminateProducer(solvedGrid));
    	}
        producers.add(new IncorrectPencilMarksProducer(solvedGrid));

        // (2) now we check for Hidden + Naked Singles
        producers.add(new HiddenSingleProducer(mConfig.useFullHouse(), mConfig.useHiddenSingle()));
        if (mConfig.useNakedSingle()) producers.add(new NakedSingleProducer());

        // (3) then we'll use more advanced solving techniques based on pencil marks to produce more hints
        producers.add(new MissingPencilMarksProducer(solvedGrid));
        addCommonHintProducers(producers, solvedGrid);

        // advanced hint producers
        // these are very slow and only used as a last resort
        //producers.add(new ChainingProducer(true, true, false, 2));
        //producers.add(new ChainingProducer(true, true, false, 3));

        // experimental hint producers
        //producers.add(new ChainingProducer(true, true, false, 4));
        //producers.add(new ChainingProducer(true, true, false, 5));
        
        // (4) last resort
        producers.add(new BruteForceProducer(solvedGrid));
        
        return producers;
    }
    
    /**
     * Return producers to check validity of a puzzle
     */
    private ArrayList<HintProducer> getCheckProducers(Grid solvedGrid) {
    	ArrayList<HintProducer> producers = new ArrayList<HintProducer>();

    	producers.add(new IncorrectDigitsProducer(solvedGrid, false));
    	producers.add(new TooFewGivensProducer());
    	if (mEliminatePencilMarks) {
            producers.add(new PencilMarks2EliminateProducer(solvedGrid));
    	}
        producers.add(new IncorrectPencilMarksProducer(solvedGrid));
    	producers.add(new SolutionProducer(false));
        
        return producers;
    }
    
    /**
     * Return producers to solve Sudokus (brute force)
     */
    private ArrayList<HintProducer> getSolverProducers(Grid solvedGrid) {
    	ArrayList<HintProducer> producers = new ArrayList<HintProducer>();

    	producers.add(new IncorrectDigitsProducer(solvedGrid, true));
    	producers.add(new TooFewGivensProducer());
    	producers.add(new SolutionProducer(true));
        
        return producers;
    }
    
    /**
     * Return producers to analyze Sudokus 
     */
    private ArrayList<HintProducer> getAnalyzeProducers(Grid solvedGrid) {
    	ArrayList<HintProducer> producers = new ArrayList<HintProducer>();
        
        // (1) first we check for incorrect/missing digits & pencil marks and for no/multiple solutions
    	// IMPORTANT: the FinalHintProducers must be the first one in the list before any other producers 
    	producers.add(new IncorrectDigitsProducer(solvedGrid, true));
    	producers.add(new TooFewGivensProducer());
    	if (mEliminatePencilMarks) {
            producers.add(new PencilMarks2EliminateProducer(solvedGrid));
    	}
        producers.add(new IncorrectPencilMarksProducer(solvedGrid));
    	producers.add(new SolutionProducer(false));

    	// MissingPencilMarksProducer must be the last of finalHintProducer because the hint is not final if running the analysis (*hack*)
        producers.add(new MissingPencilMarksProducer(solvedGrid));

        // Direct Hint Producers
        producers.add(new HiddenSingleProducer(mConfig.useFullHouse(), mConfig.useHiddenSingle()));
        if (mConfig.useNakedSingle()) producers.add(new NakedSingleProducer());
        
        addCommonHintProducers(producers, solvedGrid);
        
        // advanced hint producers
        // these are very slow and only used as a last resort
        producers.add(new ChainProducer(true, true, false, 2, mConfig));
        producers.add(new ChainProducer(true, true, false, 3, mConfig));
        
        // experimental hint producers
        producers.add(new ChainProducer(true, true, false, 4, mConfig));
        producers.add(new ChainProducer(true, true, false, 5, mConfig));
        
        return producers;
    }
    
    /**
     * Return producers to determine the difficulty of a Sudoku 
     */
    private ArrayList<HintProducer> getAnalyzeDifficultyProducers(Grid solvedGrid) {
    	ArrayList<HintProducer> producers = new ArrayList<HintProducer>();
        
        // these rules are not really solving techniques, they check the validity of the puzzle
        producers.add(new TooFewGivensProducer());
        producers.add(new IncorrectDigitsProducer(solvedGrid, true));

        // Direct Hint Producers
        producers.add(new HiddenSingleProducer(mConfig.useFullHouse(), mConfig.useHiddenSingle()));
        if (mConfig.useNakedSingle()) producers.add(new NakedSingleProducer());
        
        addCommonHintProducers(producers, solvedGrid);

        return producers;
    }

    private void addCommonHintProducers(ArrayList<HintProducer> producers, Grid solvedGrid) {
        if (mConfig.useLockedCandidates()) producers.add(new LockingProducer());								// Locked Candidates
        if (mConfig.useNakedPair()) producers.add(new NakedSubsetProducer(2));									// Naked Pair
        if (mConfig.useXWing()) producers.add(new FishProducer(2, false));										// X-Wing
        if (mConfig.useHiddenPair()) producers.add(new HiddenSubsetProducer(2));								// Hidden Pair
        if (mConfig.useFinnedXWing()) producers.add(new FishProducer(2, true));									// Finned/Sashimi X-Wing
        if (mConfig.useNakedTriple()) producers.add(new NakedSubsetProducer(3));								// Naked Triple
        if (mConfig.useSwordfish()) producers.add(new FishProducer(3, false));									// Swordfish
        if (mConfig.useHiddenTriple()) producers.add(new HiddenSubsetProducer(3));								// Hidden Triple
        if (mConfig.useFinnedSwordfish()) producers.add(new FishProducer(3, true));								// Finned/Sashimi Swordfish
        if (mConfig.useXYWing()) producers.add(new WingProducer(2));											// XY-Wing
        if (mConfig.useWWing()) producers.add(new WWingProducer());												// W-Wing
        if (mConfig.useXYZWing()) producers.add(new WingProducer(3));											// XYZ-Wing
        if (mConfig.useSueDeCoq()) producers.add(new SueDeCoqProducer());										// Sue de Coq
        if (mConfig.useALCPairs()) producers.add(new ALCProducer(2));											// Almost Locked Candidates (Pair)
        if (mConfig.useAvoidableRectangle()) producers.add(new AvoidableRectangleProducer());					// Avoidable Rectangle Type 1+2
        if (mConfig.useUniquenessTest()) producers.add(new UniquenessTestProducer());							// Uniqueness Test Type 1-5
        if (mConfig.useHiddenUniqueRectangle()) producers.add(new HiddenUniqueRectangleProducer());				// Hidden Unique Rectangle
        if (mConfig.useWXYZWing()) producers.add(new WingProducer(4));											// WXYZ-Wing
        if (mConfig.useVWXYZWing()) producers.add(new WingProducer(5));											// VWXYZ-Wing
        if (mConfig.useNakedQuad()) producers.add(new NakedSubsetProducer(4));									// Naked Quad
        if (mConfig.useUVWXYZWing()) producers.add(new WingProducer(6));										// UVWXYZ-Wing
        if (mConfig.useJellyfish()) producers.add(new FishProducer(4, false));									// Jellyfish
        if (mConfig.useTUVWXYZWing()) if (mConfig.useALCPairs()) producers.add(new WingProducer(7));			// TUVWXYZ-Wing
        if (mConfig.useALCTriple()) producers.add(new ALCProducer(3));											// Almost Locked Candidates (Triple)
        if (mConfig.useHiddenQuad()) producers.add(new HiddenSubsetProducer(4));								// Hidden Quad
        if (mConfig.useFinnedJellyfish()) producers.add(new FishProducer(4, true));								// Finned/Sashimi Jellyfish
        if (mConfig.useSTUVWXYZWing()) producers.add(new WingProducer(8));										// STUVWXYZ-Wing
        if (mConfig.useRSTUVWXYZWing()) producers.add(new WingProducer(9));										// RSTUVWXYZ-Wing
        if (mConfig.useBUG()) producers.add(new BUGProducer());													// BUG Type 1-4
        if (mConfig.useALCQuad()) producers.add(new ALCProducer(4));											// Almost Locked Candidates (Quad)
        if (mConfig.useAlignedPairExclusion()) producers.add(new AlignedPairExclusionProducer());				// Aligned Pair Exclusion
        if (mConfig.useXForcingChains() || mConfig.useXYForcingChains() ||										// Forcing X-Chain (Turbot Fish), Forcing X-Chain,
        	mConfig.useForcingChains() || mConfig.useCycles()) {												// Forcing XY-Chain (Remote Pairs), Forcing XY-Chain,
        	producers.add(new ChainProducer(false, false, false, 0, mConfig));									// Forcing Chain,					
        }																										// Bidirectional X-Cycle, Bidirectional Y-Cycle, Bidirectional Cycle
        producers.add(new ALSProducer(mConfig.useALSXZ(), mConfig.useALSXYWing()));								// ALS-XZ, ALS-XY-WING
        if (mConfig.useAlignedTripleExclusion()) producers.add(new AlignedSubsetExclusionProducer(3));			// Aligned Triple Exclusion
        if (mConfig.useNishioForcingChains()) producers.add(new ChainProducer(false, true, true, 0, mConfig));	// NishioForcingChains
        if (mConfig.useRegionForcingChains() || mConfig.useCellForcingChains()) {
        	producers.add(new ChainProducer(true, false, false, 0, mConfig));									// MultipleForcingChains:	CellForcingChains, RegionForcingChains (all have>=2 views --> multiple)
        }
        if (mConfig.useContradictionForcingChains() || mConfig.useRegionForcingChains() || mConfig.useCellForcingChains()) {
        	producers.add(new ChainProducer(true, true, false, 0, mConfig));									// DynamicCellForcingChains, DynamicRegionForcingChains, DynamicContradictionForcingChains
        }
        if (mConfig.useContradictionForcingChains() || mConfig.useDoubleForcingChains() ||
        	mConfig.useRegionForcingChains() || mConfig.useCellForcingChains()) {
        	producers.add(new ChainProducer(true, true, false, 1, mConfig));									// DynamicCellForcingChains, DynamicRegionForcingChains, DynamicContradictionForcingChains, DynamicDoubleForcingChains
        }
    }
    
	// ****************************************** Hints Methods *******************************************

    /**
     * This method get's all hints that apply to a certain puzzle.
     * Note: the hints can't be applied sequentially to solve the puzzle because every hint is
     * valid just for the current givens and not any more once one of the hints have been applied!
     * @param accu A HintsAccumulator the caller can pass as parameter if if want's to collect the hints "real-time".
     * This allows the caller to interrupt the solver any time by throwing an NoMoreHintsException
     * @return A list of all hints that can be applied to the puzzle
     */
    public List<Hint> getAllHints(HintsAccumulator accu, HintEngineListener listener) {
        if (hintProducers==null) hintProducers = getHintProducers(mSolvedGrid);
        int oldPriority = lowerPriority();
        accu = (accu==null) ? new DefaultHintsAccumulator() : accu;
        FinalHintInterceptor interceptor = new FinalHintInterceptor(accu);
        HintProducer runningProducer = null;
        try {
            for (HintProducer producer : hintProducers) {
            	runningProducer = producer;
            	if (listener!=null && runningProducer!=null) listener.onHintProducerStarted(runningProducer);
            	producer.getHints(mGrid, interceptor);
            	if (listener!=null && runningProducer!=null) listener.onHintProducerTerminated(runningProducer);
            }
        }
        catch (StopHintProductionException canHappen) {}
        catch (InterruptedException canHappen) {}
        catch (Throwable shouldNotHappen) {
        	// this could happen if a producer is still running after hint.apply() is called (and before the thread finally stops)
        	// we catch all Errors and Exception because losing a hint or two is not critical but crashes are
        	Logger.e(HintEngine.class.getSimpleName(), shouldNotHappen.getMessage(), shouldNotHappen);
        }
        finally {
            try {
                // if no hints could be found create the following warning hint
            	if (!interceptor.hasHints()) accu.add( new NoHintsWarning(mGrid) );
            } catch (StopHintProductionException canHappen) {}
        	if (listener!=null && runningProducer!=null) listener.onHintProducerTerminated(runningProducer);
            restorePriority(oldPriority);
        }
        return accu.getHints();
    }
    
	// ****************************************** Check & Analysis & Solve  *******************************************

    /**
     * This method check the validity of the puzzle.
     * @return Hint pointing out what's wrong with the puzzle. If the puzzle is OK the hint will be Null
     * @see #analyze()
     */
    public Hint check() {
        if (checkProducers==null) checkProducers = getCheckProducers(mSolvedGrid);
        SingleHintAccumulator accu = new SingleHintAccumulator();
        try {
            for (HintProducer producer : checkProducers) {
            	producer.getHints(mGrid, accu);
            }
        }
        catch (StopHintProductionException willProbablyHappen) {}
        catch (InterruptedException canHappen) {}
        return accu.getHint();
    }

    /**
     * This method solves the puzzle and create a Hint containing the
     * difficulty level and the techniques used to solve the puzzle.
     * This method uses the solve() method
     * @return Hint containing the difficulty level and the used techniques to solve the puzzle (AnalysisResult).
     * @see #solve()
     */
    public Hint analyze() {
        if (analyzeProducers==null) analyzeProducers = getAnalyzeProducers(mSolvedGrid); 
        int oldPriority = lowerPriority();
        SingleHintAccumulator accu = new SingleHintAccumulator();
        try {
            Analyzer analyzer = new Analyzer(analyzeProducers, mIsBeyondNightmare);
            analyzer.getHints(mGrid, accu);
        }
        catch (StopHintProductionException willProbablyHappen) {}
        catch (InterruptedException canHappen) {}
        catch (Throwable shouldNotHappen) {
        	// we catch all Errors and Exception because losing a hint or two
        	// is not critical but force closes are
        	Logger.e(HintEngine.class.getSimpleName(), shouldNotHappen.getMessage(), shouldNotHappen);
        }
        finally {
            restorePriority(oldPriority);
        }
        return accu.getHint();
    }

    /**
     * Get whether the grid's difficulty is between the two
     * bounds or not. If yes, return the actual difficulty.
     * If no, return a value less than <tt>min</tt> if the
     * grid is less difficult than <tt>min</tt> and a value
     * greater than <tt>max</tt> if the grid is more
     * difficult than <tt>max</tt>.
     * @param min the minimal difficulty (inclusive)
     * @param max the maximal difficulty (inclusive)
     * @return The actual difficulty if it is between the given bounds. An arbitrary out-of-bounds value else.
     */
    public double analyseDifficulty(double min, double max) {
        if (analyzeDifficultyProducers==null) analyzeDifficultyProducers = getAnalyzeDifficultyProducers(mSolvedGrid);
        int oldPriority = lowerPriority();
        try {
            double difficulty = Double.NEGATIVE_INFINITY;
            while (!isSolved()) {
                SingleHintAccumulator accu = new SingleHintAccumulator();
                try {
                    for (HintProducer producer : analyzeDifficultyProducers) {
                        producer.getHints(mGrid, accu);
                    }
                }
                catch (StopHintProductionException willHappen) {}
                Hint hint = accu.getHint();
                if (hint == null || hint instanceof FinalHint) {
                    // puzzle has no solution
                    return Double.MAX_VALUE;
                }
                Rule rule = (Rule)hint;
                double ruleDiff = rule.getDifficulty();
                difficulty = Math.max(difficulty, ruleDiff);
                if (difficulty>max) break;
                hint.apply();
            }
            return difficulty;
        }
        catch (InterruptedException canHappen) {}
        finally {
            restorePriority(oldPriority);
        }
        return Double.NEGATIVE_INFINITY;
    }

    /**
     * Solve the puzzle using brute force.
     * @return Either a SolutionHint or a WarningHint if the puzzle is not valid! 
     */
    public Hint bruteForceSolve() {
        if (solveProducers==null) solveProducers = getSolverProducers(mSolvedGrid);
        SingleHintAccumulator accu = new SingleHintAccumulator();
        try {
            for (HintProducer producer : solveProducers) {
            	producer.getHints(mGrid, accu);
            }
        }
        catch (StopHintProductionException willProbablyHappen) {}
        catch (InterruptedException canHappen) {}
        return accu.getHint();
    }

	// ****************************************** Helper Methods *******************************************

    private boolean isSolved() {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                if (mGrid.getCellValue(x, y) == 0) return false;
            }
        }
        return true;
    }

    /**
     * Lower the current thread's priority.
     * @return the previous thread's priority
     */
    private int lowerPriority() {
        try {
            int result = Thread.currentThread().getPriority();
            Thread.currentThread().setPriority((Thread.NORM_PRIORITY + Thread.MIN_PRIORITY * 2) / 3);
            return result;
        }
        catch (AccessControlException ignore) {}
        return 0;
    }

    /**
     * Reset the current thread's priority to the given value.
     * Typically, the given value is the value returned by
     * {@link #lowerPriority()}.
     * @param priority the new priority
     */
    private void restorePriority(int priority) {
        try {
            Thread.currentThread().setPriority(priority);
        }
        catch (AccessControlException ignore) {}
    }
}